#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

string longestPalindrome(string s) {
    int n = s.size();
    s = ' ' + s;
    vector<vector<bool>> f(n + 1, vector<bool>(n + 1));
    int begin = 0, len = 0;
    for (int i = n; i > 0; i--)
        for (int j = i; j <= n; j++)
        {
            if (s[i] == s[j])
                f[i][j] = i + 1 < j ? f[i + 1][j - 1] : true;
            if (f[i][j] && j - i + 1 > len)
            {
                begin = i;
                len = j - i + 1;
            }
        }
    return s.substr(begin, len);
}

